import java.util.*;

import static java.util.Collections.binarySearch;

/**
 * @Author: zhanglinxin
 * @CreateTime: 2025/2/5 10:18
 * @Description:
 * @Version: 1.0
 */
public class Solution202502 {
    /**
     * @Description: 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,2,2]
     * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
     * <p>
     * 示例 2：
     * <p>
     * 输入：nums = [0]
     * 输出：[[],[0]]
     * @param: [int[]]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     * @Author: zhanglinxin
     * @date: 2025/2/5 10:19
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 用于存储当前生成的子集
        List<Integer> t = new ArrayList<>();
        // 用于存储所有的唯一子集
        List<List<Integer>> ans = new ArrayList<>();
        // 首先对输入数组进行排序，以便于后续跳过重复子集
        Arrays.sort(nums);
        int n = nums.length;
        // 使用位掩码遍历所有可能的子集组合
        for (int mask = 0; mask < (1 << n); ++mask) {
            // 清除当前子集t的内容，准备添加新子集
            t.clear();
            boolean flag = true;
            // 遍历每一位，检查是否在当前mask中被选中
            for (int i = 0; i < n; ++i) {
                // 检查第i位是否被设置
                if ((mask & (1 << i)) != 0) {
                    // 如果当前元素和前一个相同，并且前一个没有被选择，则跳过这个组合
                    if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
                        flag = false;
                        break;
                    }
                    // 将选定的元素加入到当前子集
                    t.add(nums[i]);
                }
            }
            // 如果当前组合有效（未被标记为false），则将其加入到答案列表
            if (flag) {
                ans.add(new ArrayList<>(t));
            }
        }
        return ans;
    }

    /**
     * @Description: 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     * <p>
     * 示例 1：
     * 输入：nums = [1,1,2]
     * 输出：
     * [[1,1,2],
     * [1,2,1],
     * [2,1,1]]
     * <p>
     * 示例 2：
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     * <p>
     * 提示：
     * 1 <= nums.length <= 8
     * -10 <= nums[i] <= 10
     * @param: [int[]]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     * @Author: zhanglinxin
     * @date: 2025/2/6 09:27
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, boolean[] used) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 如果当前元素已被使用，或与前一个元素相同且前一个未被使用，则跳过
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            current.add(nums[i]);
            backtrack(result, current, nums, used);
            used[i] = false;
            current.removeLast();
        }
    }

    /**
     * @Description: 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，按 顺时针顺序螺旋排列 的 n x n 正方形矩阵 matrix 。
     * <p>
     * 示例 1：
     * <p>
     * 输入：n = 3
     * 输出：[[1,2,3],[8,9,4],[7,6,5]]
     * <p>
     * 示例 2：
     * 输入：n = 1
     * 输出：[[1]]
     */
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        boolean[][] used = new boolean[n][n];
        int num = 1;
        int direction = 1;
        int row = 0;
        int col = 0;
        while (num <= n * n) {
            matrix[row][col] = num++;
            used[row][col] = true;
            switch (direction) {
                case 1:
                    if (col + 1 < n && !used[row][col + 1]) {
                        col++;
                    } else {
                        row++;
                        direction = 2;
                    }
                    break;
                case 2:
                    if (row + 1 < n && !used[row + 1][col]) {
                        row++;
                    } else {
                        col--;
                        direction = 3;
                    }
                    break;
                case 3:
                    if (col - 1 >= 0 && !used[row][col - 1]) {
                        col--;
                    } else {
                        row--;
                        direction = 4;
                    }
                    break;
                case 4:
                    if (row - 1 >= 0 && !used[row - 1][col]) {
                        row--;
                    } else {
                        col++;
                        direction = 1;
                    }
                    break;
            }
        }

        return matrix;
    }

    public int[][] generateMatrix1(int n) {
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int[][] ans = new int[n][n];
        int i = 0;
        int j = 0;
        int di = 0;
        for (int v = 1; v <= n * n; v++) {
            ans[i][j] = v;
            int x = i + dirs[di][0];
            int y = j + dirs[di][1];
            if (x < 0 || x >= n || y < 0 || y >= n || ans[x][y] != 0) {
                di = (di + 1) % 4;
            }
            i += dirs[di][0];
            j += dirs[di][1];
        }
        return ans;
    }

    public int[][] generateMatrix2(int n) {
        int[][] matrix = new int[n][n];
        if (n == 0) {
            return matrix;
        }
        if (n == 1) {
            matrix[0][0] = 1;
            return matrix;
        }
        int count = n - 1;
        int y = 0, x = 0;
        int index = 1;
        while (index <= n * n) {
            for (int i = 0; i < count; i++) {
                matrix[y][x++] = index++;
            }
            for (int i = 0; i < count; i++) {
                matrix[y++][x] = index++;
            }
            for (int i = 0; i < count; i++) {
                matrix[y][x--] = index++;
            }
            for (int i = 0; i < count; i++) {
                matrix[y--][x] = index++;
            }
            y++;
            x++;
            if (index == n * n) {
                matrix[y][x] = index;
                break;
            }
            count -= 2;
        }
        return matrix;
    }

    /**
     * @Description: 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。
     * 机器人每次只能向下或者向右移动一步。网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
     * 返回机器人能够到达右下角的不同路径数量。
     * 测试用例保证答案小于等于 2 * 10^9。
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
     * 输出：2
     * 解释：3x3 网格的正中间有一个障碍物。
     * 从左上角到右下角一共有 2 条不同的路径：
     * 1. 向右 -> 向右 -> 向下 -> 向下
     * 2. 向下 -> 向下 -> 向右 -> 向右
     * <p>
     * 示例 2：
     * 输入：obstacleGrid = [[0,1],[0,0]]
     * 输出：1
     * <p>
     * <p>
     * 提示：
     * m == obstacleGrid.length
     * n == obstacleGrid[i].length
     * 1 <= m, n <= 100
     * obstacleGrid[i][j] 为 0 或 1
     * @param: [int[][]]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/8 10:26
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 动态规划roads存储每个点可到达的路径
        int[][] roads = new int[obstacleGrid.length][obstacleGrid[0].length];
        if (obstacleGrid[0][0] == 1 || obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) {
            // 当起始点和终结点有障碍物时没有路径
            return 0;
        }
        roads[0][0] = 1;
        // 处理第一行，由于机器人只能向右或向下，故第一行中只要出现障碍物，后面的点就不可能到达
        for (int i = 1; i < obstacleGrid[0].length; i++) {
            roads[0][i] = obstacleGrid[0][i] == 0 ? roads[0][i - 1] : 0;
        }
        // 处理第一列，由于机器人只能向右或向下，故第一列中只要出现障碍物，后面的点就不可能到达
        for (int i = 1; i < obstacleGrid.length; i++) {
            roads[i][0] = obstacleGrid[i][0] == 0 ? roads[i - 1][0] : 0;
        }

        // 处理中间的格子，只要不是障碍物，则到达该格子的路径数等于到达其左边格子的路径数加上到达其上边格子的路径数
        for (int i = 0; i < obstacleGrid.length; i++) {
            for (int j = 0; j < obstacleGrid[0].length; j++) {
                if (i != 0 && j != 0 && obstacleGrid[i][j] == 0) {
                    roads[i][j] = roads[i - 1][j] + roads[i][j - 1];
                }
            }
        }
        return roads[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }

    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        for (int i = 0; i < obstacleGrid.length; i++) {
            for (int j = 0; j < obstacleGrid[0].length; j++) {
                if (i == 0 && j == 0) {
                    obstacleGrid[i][j] ^= 1;
                } else if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                } else if (i == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i][j - 1];
                } else if (j == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j];
                } else {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                    ;
                }
            }
        }
        return obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }

    /**
     * @Description: 一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。
     * <p>
     * 它们所处的环境设定是一个 rows x cols 的方格 grid ，其中每个格子可能是一堵墙、一块地板、一位玩家（猫或者老鼠）或者食物。
     * <p>
     * 玩家由字符 'C' （代表猫）和 'M' （代表老鼠）表示。
     * 地板由字符 '.' 表示，玩家可以通过这个格子。
     * 墙用字符 '#' 表示，玩家不能通过这个格子。
     * 食物用字符 'F' 表示，玩家可以通过这个格子。
     * 字符 'C' ， 'M' 和 'F' 在 grid 中都只会出现一次。
     * 猫和老鼠按照如下规则移动：
     * <p>
     * 老鼠 先移动 ，然后两名玩家轮流移动。
     * 每一次操作时，猫和老鼠可以跳到上下左右四个方向之一的格子，他们不能跳过墙也不能跳出 grid 。
     * catJump 和 mouseJump 是猫和老鼠分别跳一次能到达的最远距离，它们也可以跳小于最大距离的长度。
     * 它们可以停留在原地。
     * 老鼠可以跳跃过猫的位置。
     * 游戏有 4 种方式会结束：
     * <p>
     * 如果猫跟老鼠处在相同的位置，那么猫获胜。
     * 如果猫先到达食物，那么猫获胜。
     * 如果老鼠先到达食物，那么老鼠获胜。
     * 如果老鼠不能在 1000 次操作以内到达食物，那么猫获胜。
     * 给你 rows x cols 的矩阵 grid 和两个整数 catJump 和 mouseJump ，双方都采取最优策略，如果老鼠获胜，那么请你返回 true ，否则返回 false 。
     * <p>
     * 示例 1：
     * 输入：grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
     * 输出：true
     * 解释：猫无法抓到老鼠，也没法比老鼠先到达食物。
     * <p>
     * 示例 2：
     * 输入：grid = ["M.C...F"], catJump = 1, mouseJump = 4
     * 输出：true
     * <p>
     * 示例 3：
     * 输入：grid = ["M.C...F"], catJump = 1, mouseJump = 3
     * 输出：false
     * <p>
     * 示例 4：
     * 输入：grid = ["C...#","...#F","....#","M...."], catJump = 2, mouseJump = 5
     * 输出：false
     * <p>
     * 示例 5：
     * 输入：grid = [".M...","..#..","#..#.","C#.#.","...#F"], catJump = 3, mouseJump = 1
     * 输出：true
     * @param: [java.lang.String[], int, int]
     * @return: boolean
     * @Author: zhanglinxin
     * @date: 2025/2/11 08:46
     */
    // 左右上下
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
        int m = grid.length, n = grid[0].length();
        // 鼠和猫分别建图
        List<Integer>[] gMouse = new ArrayList[m * n];
        List<Integer>[] gCat = new ArrayList[m * n];
        Arrays.setAll(gMouse, i -> new ArrayList<>());
        Arrays.setAll(gCat, i -> new ArrayList<>());
        int mx = 0, my = 0, cx = 0, cy = 0, fx = 0, fy = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '#') {
                    // 墙
                    continue;
                }
                if (c == 'M') {
                    // 鼠的位置
                    mx = i;
                    my = j;
                } else if (c == 'C') {
                    // 猫的位置
                    cx = i;
                    cy = j;
                } else if (c == 'F') {
                    // 食物（洞）的位置
                    fx = i;
                    fy = j;
                }
                // 二维坐标 (i,j) 映射为一维坐标 v
                int v = i * n + j;
                for (int[] dir : DIRS) {
                    // 枚举左右上下四个方向
                    jump(grid, mouseJump, m, n, gMouse, i, j, v, dir);
                    jump(grid, catJump, m, n, gCat, i, j, v, dir);
                }
            }
        }

        // 判断是否鼠赢
        return catMouseGame(gMouse, gCat, mx * n + my, cx * n + cy, fx * n + fy) == 1;
    }

    private void jump(String[] grid, int mouseJump, int m, int n, List<Integer>[] gMouse, int i, int j, int v, int[] dir) {
        for (int k = 0; k <= mouseJump; k++) {
            // 枚举跳跃长度
            int x = i + k * dir[0], y = j + k * dir[1];
            if (x < 0 || x >= m || y < 0 || y >= n || grid[x].charAt(y) == '#') {
                // 出界或者遇到墙
                break;
            }
            // 连边
            gMouse[v].add(x * n + y);
        }
    }

    // 913. 猫和老鼠
    private int catMouseGame(List<Integer>[] gMouse, List<Integer>[] gCat, int mouseStart, int catStart, int hole) {
        int n = gMouse.length;
        int[][][] deg = new int[n][n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                deg[i][j][0] = gMouse[i].size();
                deg[i][j][1] = gCat[j].size();
            }
        }

        int[][][] winner = new int[n][n][2];
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 鼠到达洞中（此时轮到猫移动），鼠获胜
            winner[hole][i][1] = 1;
            // 猫到达洞中（此时轮到鼠移动），猫获胜
            winner[i][hole][0] = 2;
            // 猫和鼠出现在同一个节点，无论轮到谁移动，都是猫获胜
            winner[i][i][0] = winner[i][i][1] = 2;
            q.offer(new int[]{hole, i, 1});
            q.offer(new int[]{i, hole, 0});
            q.offer(new int[]{i, i, 0});
            q.offer(new int[]{i, i, 1});
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int mouse = cur[0], cat = cur[1], turn = cur[2];
            // 最终谁赢了
            int win = winner[mouse][cat][turn];
            for (int[] pre : getPreStates(mouse, cat, turn, gMouse, gCat, winner)) {
                int preMouse = pre[0], preCat = pre[1], preTurn = turn ^ 1;
                // 情况一：如果上一回合鼠从 pre 移动到 cur，最终鼠赢，那么标记 pre 状态的 winner = 鼠
                // 情况二：如果上一回合猫从 pre 移动到 cur，最终猫赢，那么标记 pre 状态的 winner = 猫
                // 情况三：如果上一回合鼠从 pre 移动到 cur，最终猫赢，那么待定，直到我们发现从 pre 出发能到达的状态都是猫赢，那么标记 pre 状态的 winner = 猫
                // 情况四：如果上一回合猫从 pre 移动到 cur，最终鼠赢，那么待定，直到我们发现从 pre 出发能到达的状态都是鼠赢，那么标记 pre 状态的 winner = 鼠
                if (preTurn == win - 1 || --deg[preMouse][preCat][preTurn] == 0) {
                    winner[preMouse][preCat][preTurn] = win;
                    // 继续倒推
                    q.offer(new int[]{preMouse, preCat, preTurn});
                }
            }
        }

        // 鼠在节点 mouseStart，猫在节点 catStart，当前轮到鼠移动
        // 返回最终谁赢了（或者平局）
        return winner[mouseStart][catStart][0];
    }

    // 获取 (mouse, cat, turn) 的上个状态（值尚未确定）
    private List<int[]> getPreStates(int mouse, int cat, int turn, List<Integer>[] gMouse, List<Integer>[] gCat, int[][][] winner) {
        List<int[]> preStates = new ArrayList<>();
        if (turn == 0) {
            // 当前轮到鼠移动
            for (int preCat : gCat[cat]) {
                // 上一轮猫的位置
                if (winner[mouse][preCat][1] == 0) {
                    // 猫无法移动到洞中
                    preStates.add(new int[]{mouse, preCat});
                }
            }
        } else { // 当前轮到猫移动
            for (int preMouse : gMouse[mouse]) {
                // 上一轮鼠的位置
                if (winner[preMouse][cat][0] == 0) {
                    preStates.add(new int[]{preMouse, cat});
                }
            }
        }
        return preStates;
    }

    /**
     * @Description: 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
     * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
     * @param: [int]
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     * @Author: zhanglinxin
     * @date: 2025/2/12 07:50
     */
    public List<List<Integer>> generate(int numRows) {
        Integer[][] dp = new Integer[numRows][];
        for (int i = 0; i < numRows; i++) {
            dp[i] = new Integer[i + 1];
            dp[i][0] = 1;
            dp[i][i] = 1;
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        for (Integer[] row : dp) {
            result.add(Arrays.asList(row));
        }
        // 返回结果列表
        return result;
    }

    /**
     * @Description: 给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。
     * 你可以进行如下操作至多 maxOperations 次：
     * 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
     * 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。
     * 你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。
     * 请你返回进行上述操作后的最小开销。
     * <p>
     * 示例 1：
     * 输入：nums = [9], maxOperations = 2
     * 输出：3
     * 解释：
     * - 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
     * - 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
     * 装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。
     * <p>
     * 示例 2：
     * 输入：nums = [2,4,8,2], maxOperations = 4
     * 输出：2
     * 解释：
     * - 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
     * - 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
     * - 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
     * - 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
     * 装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。
     * <p>
     * 示例 3：
     * 输入：nums = [7,17], maxOperations = 2
     * 输出：7
     * <p>
     * <p>
     * 提示：
     * 1 <= nums.length <= 105
     * 1 <= maxOperations, nums[i] <= 109
     * @param: [int[], int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/12 08:00
     */
    public int minimumSize(int[] nums, int maxOperations) {
        int left = 1, right = Arrays.stream(nums).max().getAsInt();
        int ans = 0;
        while (left <= right) {
            int y = (left + right) / 2;
            long ops = 0;
            // 如果 y=y0 是一个满足要求的答案，那么所有大于 y0 的 y 同样也是满足要求的。
            // 因此存在一个 y=yopt，使得当 y≥yopt 时都是满足要求的，当 y<yopt 时都是不满足要求的。
            // 这个 yopt 就是最终的答案。因此，我们可以通过二分查找的方式得到答案。
            // 二分查找的下界为 1，上界为数组 nums 中的最大值，即单个袋子中最多的球数。
            // 当我们二分查找到 y 时，对于第 i 个袋子，其中有 nums[i] 个球，那么需要的操作次数为：ops += (x - 1) / y
            for (int x : nums) {
                ops += (x - 1) / y;
            }
            if (ops <= maxOperations) {
                ans = y;
                right = y - 1;
            } else {
                left = y + 1;
            }
        }
        return ans;
    }

    /**
     * @Description: 你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束
     * （包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。
     * 另有无限数量的盒子，编号从 1 到 infinity 。
     * 你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。
     * 例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。
     * 给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，
     * 只需返回其中任一盒子的小球数量。
     * <p>
     * <p>
     * 示例 1：
     * 输入：lowLimit = 1, highLimit = 10
     * 输出：2
     * 解释：
     * 盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
     * 小球数量：2 1 1 1 1 1 1 1 1 0  0  ...
     * 编号 1 的盒子放有最多小球，小球数量为 2 。
     * <p>
     * 示例 2：
     * 输入：lowLimit = 5, highLimit = 15
     * 输出：2
     * 解释：
     * 盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
     * 小球数量：1 1 1 1 2 2 1 1 1 0  0  ...
     * 编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。
     * <p>
     * 示例 3：
     * 输入：lowLimit = 19, highLimit = 28
     * 输出：2
     * 解释：
     * 盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ...
     * 小球数量：0 1 1 1 1 1 1 1 1 2  0  0  ...
     * 编号 10 的盒子放有最多小球，小球数量为 2 。
     * <p>
     * 提示：
     * 1 <= lowLimit <= highLimit <= 105
     * @param: [int, int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/13 10:42
     */
    public int countBalls(int lowLimit, int highLimit) {
        int[] cnt = new int[46];
        for (int i = lowLimit; i <= highLimit; i++) {
            int j = i, s = 0;
            while (j != 0) {
                s += j % 10;
                j /= 10;
            }
            cnt[s]++;
        }
        int ans = 0;
        for (int i = 0; i < 46; i++) {
            ans = Math.max(ans, cnt[i]);
        }
        return ans;
    }

    /**
     * @Description: 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
     * @param: [int]
     * @return: java.util.List<java.lang.Integer>
     * @Author: zhanglinxin
     * @date: 2025/2/13 11:11
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        row.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i));
        }
        return row;
    }

    /**
     * @Description: 在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。
     * Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。
     * 已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
     * 给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
     * <p>
     * 示例 1：
     * 输入：position = [1,2,3,4,7], m = 3
     * 输出：3
     * 解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。
     * <p>
     * 示例 2：
     * 输入：position = [5,4,3,2,1,1000000000], m = 2
     * 输出：999999999
     * 解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。
     * <p>
     * 提示：
     * n == position.length
     * 2 <= n <= 10^5
     * 1 <= position[i] <= 10^9
     * 所有 position 中的整数 互不相同 。
     * 2 <= m <= position.length
     * @param: [int[], int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/14 08:34
     */
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        //磁力至少为1，最多为position[position.length - 1] - position[0]
        int left = 1, right = position[position.length - 1] - position[0];
        while (left < right) {
            // 假设最小磁力为mid
            int mid = (left + right + 1) / 2;
            // 判断当磁力为mid时
            // 如果可以满足条件，则说明mid可以更大，所以left = mid
            if (check(position, m, mid)) {
                left = mid;
            } else {
                // 如果不能满足条件，则说明mid太小，所以right = mid - 1
                right = mid - 1;
            }
        }
        return left;
    }

    public boolean check(int[] position, int m, int mid) {
        // 第一个球放在第一个篮子
        int cnt = 1, pre = position[0];
        for (int i = 1; i < position.length; i++) {
            // 如果当前篮子与上一个篮子的距离大于等于mid，则可以放一个球
            if (position[i] - pre >= mid) {
                cnt++;
                pre = position[i];
            }
        }
        return cnt >= m;
    }

    /**
     * @Description: 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
     * <p>
     * 示例 1：
     * 输入：n = 2
     * 输出：[0,1,1]
     * 解释：
     * 0 --> 0
     * 1 --> 1
     * 2 --> 10
     * <p>
     * 示例 2：
     * 输入：n = 5
     * 输出：[0,1,1,2,1,2]
     * 解释：
     * 0 --> 0
     * 1 --> 1
     * 2 --> 10
     * 3 --> 11
     * 4 --> 100
     * 5 --> 101
     * <p>
     * 提示：
     * 0 <= n <= 105
     * <p>
     * 进阶：
     * 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
     * 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）
     * @param: [int]
     * @return: int[]
     * @Author: zhanglinxin
     * @date: 2025/2/14 08:53
     */
    public int[] countBits(int n) {
        // 创建一个长度为n+1的数组来保存结果，因为我们需要包括0到n的所有数字。
        int[] res = new int[n + 1];
        // 初始化0的二进制表示中1的个数为0。这是已知的事实，因此可以直接设置。
        res[0] = 0;
        // 遍历从1到n的所有数字，计算它们的二进制表示中1的个数。
        for (int i = 1; i < n + 1; i++) {
            // 如果i是奇数，则它的二进制表示比前一个偶数多一个1（即最低位为1）。
            if (i % 2 == 1) {
                res[i] = res[i - 1] + 1;
            } else {
                // 如果i是偶数，则它的二进制表示中1的个数等于i除以2的结果的二进制表示中1的个数。
                // 这是因为将一个偶数右移一位（即除以2）不会改变它二进制表示中1的个数。
                res[i] = res[i / 2];
            }
        }
        // 返回结果数组，包含了从0到n每个数字的二进制表示中1的个数。
        return res;
    }

    /**
     * @Description: 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
     * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
     * （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
     * 进阶：
     * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
     * <p>
     * 示例 1：
     * 输入：s = "abc", t = "ahbgdc"
     * 输出：true
     * <p>
     * 示例 2：
     * 输入：s = "axc", t = "ahbgdc"
     * 输出：false
     * <p>
     * 提示：
     * 0 <= s.length <= 100
     * 0 <= t.length <= 10^4
     * 两个字符串都只由小写字符组成。
     * @param: [java.lang.String, java.lang.String]
     * @return: boolean
     * @Author: zhanglinxin
     * @date: 2025/2/14 10:28
     */
    public boolean isSubsequence(String origin, String isSub) {
        char[] sCharArray = origin.toCharArray();
        char[] tCharArray = isSub.toCharArray();
        int sIndex = 0;
        int tIndex = 0;
        while (sIndex < sCharArray.length && tIndex < tCharArray.length) {
            if (sCharArray[sIndex] == tCharArray[tIndex]) {
                sIndex++;
                tIndex++;
            } else {
                tIndex++;
            }
        }
        return sIndex == sCharArray.length;
    }

    /**
     * @Description: 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。
     * 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
     * F(0) = 0，F(1) = 1
     * F(n) = F(n - 1) + F(n - 2)，其中 n > 1
     * 给定 n ，请计算 F(n) 。
     * <p>
     * 示例 1：
     * 输入：n = 2
     * 输出：1
     * 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
     * <p>
     * 示例 2：
     * 输入：n = 3
     * 输出：2
     * 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
     * <p>
     * 示例 3：
     * 输入：n = 4
     * 输出：3
     * 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
     * @param: [int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/14 10:35
     */
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int i1 = 0, i2 = 1, re = 0;
        for (int i = 2; i <= n; i++) {
            re = i1 + i2;
            i1 = i2;
            i2 = re;
        }
        return re;
    }

    /**
     * @Description: 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
     * 请你找到并返回这个整数
     * <p>
     * 示例：
     * 输入：arr = [1,2,2,6,6,6,6,7,10]
     * 输出：6
     * <p>
     * 提示：
     * 1 <= arr.length <= 10^4
     * 0 <= arr[i] <= 10^5
     * @param: [int[]]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/17 08:25
     */
    public int findSpecialInteger(int[] arr) {
        Arrays.sort(arr);
        int length = arr.length;
        int quarter = length / 4;
        int count = 1;
        int res = arr[0];
        for (int i = 1; i < length; i++) {
            if (count > quarter) {
                return res;
            }
            if (res == arr[i]) {
                count++;
            } else {
                count = 1;
                res = arr[i];
            }
        }
        return res;
    }

    public int findSpecialInteger1(int[] arr) {
        int pin = 0, n = arr.length;
        for (int i = 0; i < n; i++) {
            if (i > 0 && arr[i] != arr[i - 1]) {
                pin = 0;
            }
            pin += 1;
            if (pin > n / 4) {
                return arr[i];
            }
        }
        return arr[n - 1];
    }

    /**
     * @Description: 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
     * 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     * 请你计算并返回达到楼梯顶部的最低花费。
     * <p>
     * 示例 1：
     * 输入：cost = [10,15,20]
     * 输出：15
     * 解释：你将从下标为 1 的台阶开始。
     * - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
     * 总花费为 15 。
     * <p>
     * 示例 2：
     * 输入：cost = [1,100,1,1,1,100,1,1,100,1]
     * 输出：6
     * 解释：你将从下标为 0 的台阶开始。
     * - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
     * - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
     * - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
     * - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
     * - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
     * - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
     * 总花费为 6 。
     * <p>
     * 提示：
     * 2 <= cost.length <= 1000
     * 0 <= cost[i] <= 999
     * @param: [int[]]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/17 09:38
     */
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        // 保存到达每个位置的最低消耗
        int[] minCosts = new int[length + 1];
        minCosts[0] = 0;
        minCosts[1] = 0;
        for (int i = 2; i <= length; i++) {
            minCosts[i] = Math.min(minCosts[i - 1] + cost[i - 1], minCosts[i - 2] + cost[i - 2]);
        }
        return minCosts[length];
    }

    /**
     * @Description: 请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
     * 子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
     * 请你实现 RangeFreqQuery 类：
     * RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
     * int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。
     * 一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。
     * @param: [int[]]
     * @return:
     * @Author: zhanglinxin
     * @date: 2025/2/18 07:48
     */
    private HashMap<Integer, List<Integer>> map = new HashMap<>();

    public Solution202502(int[] arr) {
        map = new HashMap<>();
        for (int i = 0; i < arr.length; ++i) {
            map.putIfAbsent(arr[i], new ArrayList<>());
            map.get(arr[i]).add(i);
        }
    }

    public int query(int left, int right, int value) {
        List<Integer> list = map.get(value);
        if (list == null) {
            return 0;
        }
        // > right 等价于 >= right+1
        return lowerBound(list, right + 1) - lowerBound(list, left);
    }

    // 开区间写法
    // 请看 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(List<Integer> a, int target) {
        // 开区间 (left, right)
        int left = -1;
        int right = a.size();
        // 区间不为空
        while (left + 1 < right) {
            // 循环不变量：
            // a[left] < target
            // a[right] >= target
            int mid = (left + right) >>> 1;
            if (a.get(mid) < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        // right 是最小的满足 a[right] >= target 的下标
        return right;
    }

    /**
     * @Description: 爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
     * 最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：
     * 选出任一 x，满足 0 < x < n 且 n % x == 0 。
     * 用 n - x 替换黑板上的数字 n 。
     * 如果玩家无法执行这些操作，就会输掉游戏。
     * 只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。
     * <p>
     * 示例 1：
     * 输入：n = 2
     * 输出：true
     * 解释：爱丽丝选择 1，鲍勃无法进行操作。
     * <p>
     * 示例 2：
     * 输入：n = 3
     * 输出：false
     * 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
     * <p>
     * 提示：
     * 1 <= n <= 1000
     * @param: [int]
     * @return: boolean
     * @Author: zhanglinxin
     * @date: 2025/2/18 10:24
     */
    public boolean divisorGame(int n) {
        /*
        博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试：
            n=1的时候，区间(0,1)中没有整数是n的因数，所以此时Alice败。
            n=2的时候，Alice只能拿1，n变成1，Bob无法继续操作，故Alice胜。
            n=3的时候，Alice只能拿1，n变成2，根据n=2的结论，我们知道此时Bob会获胜，Alice败。
            n=4的时候，Alice能拿1或2，如果Alice拿1，根据n=3的结论，Bob会失败，Alice会获胜。
            n=5的时候，Alice只能拿1，根据n=4的结论，Alice会失败。
            ......
        写到这里，也许你有了一些猜想。没关系，请大胆地猜想，在这种情况下大胆地猜想是 AC 的第一步。
        也许你会发现这样一个现象：n为奇数的时候Alice（先手）必败，n为偶数的时候Alice必胜。

        这个猜想是否正确呢？下面我们来想办法证明它:
        1.n=1和n=2时结论成立。
        2.n>2时，假设n≤k时该结论成立，则n=k+1时：
        如果k为偶数，则k+1为奇数，x是k+1的因数，只可能是奇数，而奇数减去奇数等于偶数，且k+1−x≤k，故轮到Bob的时候都是偶数。
        而根据我们的猜想假设n≤k的时候偶数的时候先手必胜，故此时无论Alice拿走什么，Bob都会处于必胜态，所以Alice处于必败态。
        如果k为奇数，则k+1为偶数，x可以是奇数也可以是偶数，若Alice减去一个奇数，那么k+1−x是一个小于等于k的奇数，
        此时Bob占有它，处于必败态，则Alice处于必胜态。
        综上所述，这个猜想是正确的。
         */
        return n % 2 == 0;
    }

    /**
     * @Description: 给定 m 个数组，每个数组都已经按照升序排好序了。
     * 现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。
     * 返回最大距离。
     * <p>
     * 示例 1：
     * 输入：[[1,2,3],[4,5],[1,2,3]]
     * 输出：4
     * 解释：
     * 一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。
     * <p>
     * 示例 2：
     * 输入：arrays = [[1],[1]]
     * 输出：0
     * @param: [java.util.List<java.util.List < java.lang.Integer>>]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/19 07:59
     */
    public int maxDistance(List<List<Integer>> arrays) {
        int max = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int maxPath = 0, minPath = 0;
        int res = 0;
        for (int i = 0; i < arrays.size(); i++) {
            if (max < arrays.get(i).getLast()) {
                max = arrays.get(i).getLast();
                maxPath = i;
            }
            if (min2 > arrays.get(i).getFirst()) {
                min2 = arrays.get(i).getFirst();
                minPath = i;
            }

        }
        if (maxPath != minPath) {
            return max - min2;
        }
        for (int i = 0; i < arrays.size(); i++) {
            if (maxPath == i) {
                continue;
            }
            res = Math.max(res, max - Math.min(min, arrays.get(i).getFirst()));
        }
        for (int i = 0; i < arrays.size(); i++) {
            if (minPath == i) {
                continue;
            }
            res = Math.max(res, Math.max(max2, arrays.get(i).getLast()) - min2);
        }
        return res;
    }

    public int maxDistance1(List<List<Integer>> arrays) {
        int mx = Integer.MIN_VALUE, mn = Integer.MAX_VALUE;
        int mxi = 0, mni = 0;
        int n = arrays.size();
        for (int i = 0; i < n; ++i) {
            List<Integer> row = arrays.get(i);
            int first = row.getFirst();
            int last = row.getLast();
            if (first < mn) {
                mn = first;
                mni = i;
            }
            if (last > mx) {
                mx = last;
                mxi = i;
            }
        }
        if (mxi != mni) {
            return mx - mn;
        }
        int mx2 = Integer.MIN_VALUE, mn2 = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            if (i == mxi) {
                continue;
            }
            List<Integer> row = arrays.get(i);
            mx2 = Math.max(mx2, row.getLast());
            mn2 = Math.min(mn2, row.getFirst());
        }
        return Math.max(mx2 - mn, mx - mn2);
    }

    Solution202502(HashMap<Integer, List<Integer>> map) {
        this.map = map;
    }

    /**
     * @Description: 泰波那契序列 Tn 定义如下：
     * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
     * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
     * <p>
     * 示例 1：
     * 输入：n = 4
     * 输出：4
     * 解释：
     * T_3 = 0 + 1 + 1 = 2
     * T_4 = 1 + 1 + 2 = 4
     * <p>
     * 示例 2：
     * 输入：n = 25
     * 输出：1389537
     * <p>
     * 提示：
     * 0 <= n <= 37
     * 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
     * @param: [int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/19 09:52
     */
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        }
        int t1 = 0, t2 = 1, t3 = 1, res = 0;
        for (int i = 3; i < n; i++) {
            res = t1 + t2 + t3;
            t1 = t2;
            t2 = t3;
            t3 = res;
        }
        return res;
    }

    /**
     * @Description: 给你一个 正 整数 n 。
     * 用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。
     * 用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。
     * 返回整数数组 answer ，其中 answer = [even, odd] 。
     * <p>
     * 示例 1：
     * 输入：n = 17
     * 输出：[2,0]
     * 解释：17 的二进制形式是 10001 。
     * 下标 0 和 下标 4 对应的值为 1 。
     * 共有 2 个偶数下标，0 个奇数下标。
     * <p>
     * 示例 2：
     * 输入：n = 2
     * 输出：[0,1]
     * 解释：2 的二进制形式是 10 。
     * 下标 1 对应的值为 1 。
     * 共有 0 个偶数下标，1 个奇数下标。
     * <p>
     * 提示：
     * 1 <= n <= 1000
     * @param: [int]
     * @return: int[]
     * @Author: zhanglinxin
     * @date: 2025/2/20 07:49
     */
    public int[] evenOddBit(int n) {
        int[] res = new int[2];
        int i = 0;
        while (n > 0) {
            res[i] += n & 1;
            n >>= 1;
            i ^= 1;
        }
        return res;
    }

    /**
     * @Description: 给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。
     * 单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。
     * 给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。
     * <p>
     * 示例 1：
     * 输入：sequence = "ababc", word = "ab"
     * 输出：2
     * 解释："abab" 是 "ababc" 的子字符串。
     * <p>
     * 示例 2：
     * 输入：sequence = "ababc", word = "ba"
     * 输出：1
     * 解释："ba" 是 "ababc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。
     * <p>
     * 示例 3：
     * 输入：sequence = "ababc", word = "ac"
     * 输出：0
     * 解释："ac" 不是 "ababc" 的子字符串。
     * <p>
     * 提示：
     * 1 <= sequence.length <= 100
     * 1 <= word.length <= 100
     * sequence 和 word 都只包含小写英文字母。
     * @param: [java.lang.String, java.lang.String]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/20 08:06
     */
    public int maxRepeating(String sequence, String word) {
        if (word.length() > sequence.length()) {
            return 0;
        }
        if (word.length() == sequence.length()) {
            if (word.equals(sequence)) {
                return 1;
            } else {
                return 0;
            }
        }
        int res = 0;
        // String.repeat() 此方法返回一个字符串，该字符串的值是给定字符串的重复 count 次的串联。如果字符串为空或 count 为零，则返回空字符串。
        while (sequence.contains(word.repeat(res + 1))) {
            res++;
        }
        return res;
    }

    /**
     * @Description: 给你一个下标从 0 开始的字符串数组 words ，和一个下标从 0 开始的 二进制 数组 groups ，两个数组长度都是 n 。
     * 你需要从 words 中选出 最长子序列。如果对于序列中的任何两个连续串，二进制数组 groups 中它们的对应元素不同，则 words 的子序列是不同的。
     * 正式来说，你需要从下标 [0, 1, ..., n - 1] 中选出一个 最长子序列 ，将这个子序列记作长度为 k 的 [i0, i1, ..., ik - 1] ，
     * 对于所有满足 0 <= j < k - 1 的 j 都有 groups[ij] != groups[ij + 1] 。
     * 请你返回一个字符串数组，它是下标子序列 依次 对应 words 数组中的字符串连接形成的字符串数组。如果有多个答案，返回 任意 一个。
     * 注意：words 中的元素是不同的 。
     * <p>
     * 示例 1：
     * 输入：words = ["e","a","b"], groups = [0,0,1]
     * 输出：["e","b"]
     * 解释：一个可行的子序列是 [0,2] ，因为 groups[0] != groups[2] 。
     * 所以一个可行的答案是 [words[0],words[2]] = ["e","b"] 。
     * 另一个可行的子序列是 [1,2] ，因为 groups[1] != groups[2] 。
     * 得到答案为 [words[1],words[2]] = ["a","b"] 。
     * 这也是一个可行的答案。
     * 符合题意的最长子序列的长度为 2 。
     * <p>
     * 示例 2：
     * 输入：words = ["a","b","c","d"], groups = [1,0,1,1]
     * 输出：["a","b","c"]
     * 解释：一个可行的子序列为 [0,1,2] 因为 groups[0] != groups[1] 且 groups[1] != groups[2] 。
     * 所以一个可行的答案是 [words[0],words[1],words[2]] = ["a","b","c"] 。
     * 另一个可行的子序列为 [0,1,3] 因为 groups[0] != groups[1] 且 groups[1] != groups[3] 。
     * 得到答案为 [words[0],words[1],words[3]] = ["a","b","d"] 。
     * 这也是一个可行的答案。
     * 符合题意的最长子序列的长度为 3 。
     * <p>
     * 提示：
     * 1 <= n == words.length == groups.length <= 100
     * 1 <= words[i].length <= 10
     * groups[i] 是 0 或 1。
     * words 中的字符串 互不相同 。
     * words[i] 只包含小写英文字母。
     * @param: [java.lang.String[], int[]]
     * @return: java.util.List<java.lang.String>
     * @Author: zhanglinxin
     * @date: 2025/2/20 08:40
     */
    public List<String> getLongestSubsequence(String[] words, int[] groups) {
        List<String> ans = new ArrayList<>();
        int n = words.length;
        for (int i = 0; i < n; i++) {
            if (i == n - 1 || groups[i] != groups[i + 1]) {
                ans.add(words[i]);
            }
        }
        return ans;
    }

    /**
     * @Description: 给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。
     * floor[i] = '0' 表示地板上第 i 块砖块的颜色是 黑色 。
     * floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。
     * 同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。
     * 请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。
     * 请你返回没被覆盖的白色砖块的 最少 数目。
     * <p>
     * 示例 1：
     * 输入：floor = "10110101", numCarpets = 2, carpetLen = 2
     * 输出：2
     * 解释：
     * 上图展示了剩余 2 块白色砖块的方案。
     * 没有其他方案可以使未被覆盖的白色砖块少于 2 块。
     * <p>
     * 示例 2：
     * 输入：floor = "11111", numCarpets = 2, carpetLen = 3
     * 输出：0
     * 解释：
     * 上图展示了所有白色砖块都被覆盖的一种方案。
     * 注意，地毯相互之间可以覆盖。
     * <p>
     * 提示：
     * 1 <= carpetLen <= floor.length <= 1000
     * floor[i] 要么是 '0' ，要么是 '1' 。
     * 1 <= numCarpets <= 1000
     * @param: [java.lang.String, int, int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/21 07:42
     */
    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        int n = floor.length();
        if (numCarpets * carpetLen >= n) {
            return 0;
        }
        int[] s = new int[n];
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i] = floor.charAt(i) - '0';
            dp[i + 1] = dp[i] + s[i];
        }
        for (int j = 1; j <= numCarpets; j++) {
            int[] t = new int[n + 1];
            for (int i = j * carpetLen; i < n; i++) {
                t[i + 1] = Math.min(t[i] + s[i], dp[i - carpetLen + 1]);
            }
            dp = t;
        }
        return dp[n];
    }

    /**
     * @Description: 小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：
     * 1.有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
     * 2.每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
     * 3.每轮信息必须需要传递给另一个人，且信息可重复经过同一个人
     * <p>
     * 给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。
     * 返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。
     * <p>
     * 示例 1：
     * 输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
     * 输出：3
     * 解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。
     * 示例 2：
     * 输入：n = 3, relation = [[0,2],[2,1]], k = 2
     * 输出：0
     * 解释：信息不能从小 A 处经过 2 轮传递到编号 2
     * <p>
     * 限制：
     * 2 <= n <= 10
     * 1 <= k <= 5
     * 1 <= relation.length <= 90, 且 relation[i].length == 2
     * 0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]
     * @param: [int, int[][], int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/21 07:51
     */
    public int numWays(int n, int[][] relation, int k) {
        // dp[i][j]，i表示第i轮，j表示第j个人,表示经过i轮传递，信息传递到j的方案数，
        int[][] dp = new int[k + 1][n];
        // 初始化,第0轮，信息传递到0的方案数为1
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            for (int[] r : relation) {
                // 第i轮，信息传递到r[1]的方案数，等于 第i-1轮，信息传递到r[0]的方案数
                dp[i][r[1]] += dp[i - 1][r[0]];
            }
        }
        return dp[k][n - 1];
    }

    /**
     * @Description: 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
     * <p>
     * 示例 1:
     * 输入: n = 2
     * 输出: [0,1,1]
     * 解释:
     * 0 --> 0
     * 1 --> 1
     * 2 --> 10
     * <p>
     * 示例 2:
     * 输入: n = 5
     * 输出: [0,1,1,2,1,2]
     * 解释:
     * 0 --> 0
     * 1 --> 1
     * 2 --> 10
     * 3 --> 11
     * 4 --> 100
     * 5 --> 101
     * @param: [int]
     * @return: int[]
     * @Author: zhanglinxin
     * @date: 2025/2/21 08:14
     */
    public int[] countBits1(int n) {
        int[] bits = new int[n + 1];
        bits[0] = 0;
        for (int i = 1; i <= n; i++) {
            // 对于所有的数字，只有奇数和偶数两种：
            //奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
            //偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。
            // 因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
            //所以我们可以得到如下的状态转移方程：
            //dp[i] = dp[i-1]，当i为奇数，
            // 对于奇数而言，(i-1)/2等价于i/2，因为java除是取整的，所以
            //dp[i] = dp[i/2] + 1，当i为奇数
            //dp[i] = dp[i/2]，当i为偶数
            //上面的方程还可进一步合并为：
            //dp[i] = dp[i/2] + i % 2 ，，
            //通过位运算进一步优化：
            //i / 2 可以通过 i >> 1 得到；
            //i % 2 可以通过 i & 1 得到；
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }

    String[] values;
    int valuesId;

//    public Solution202502(int n) {
//        values = new String[n + 1];
//        valuesId = 1;
//    }

    /**
     * @Description: 有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。
     * 设计一个流，以 任意 顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。
     * 实现 OrderedStream 类：
     * OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
     * String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
     * 如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，
     * 并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个  id + 1 。
     * 否则，返回一个空列表。
     * @param: [int, java.lang.String]
     * @return: java.util.List<java.lang.String>
     * @Author: zhanglinxin
     * @date: 2025/2/24 07:58
     */
    public List<String> insert(int idKey, String value) {
        values[idKey - 1] = value;
        List<String> list = new ArrayList<>();
        while (valuesId < values.length && values[valuesId - 1] != null) {
            list.add(values[valuesId - 1]);
            valuesId++;
        }
        return list;
    }

    /**
     * @Description: 给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。
     * 请你设计一个具备以下功能的内存分配器：
     * 分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。
     * 释放 给定 id mID 对应的所有内存单元。
     * 注意：
     * 多个块可以被分配到同一个 mID 。
     * 你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。
     * 实现 Allocator 类：
     * Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
     * int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于  最左侧 的块，分配并赋 id mID 。
     * 返回块的第一个下标。如果不存在这样的块，返回 -1 。
     * int freeMemory(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。
     * <p>
     * 示例：
     * 输入
     * ["Allocator", "allocate", "allocate", "allocate", "freeMemory", "allocate", "allocate", "allocate", "freeMemory", "allocate", "freeMemory"]
     * [[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
     * 输出
     * [null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]
     * <p>
     * 解释
     * Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
     * loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
     * loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
     * loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
     * loc.freeMemory(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。
     * loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
     * loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
     * loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
     * loc.freeMemory(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
     * loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
     * loc.freeMemory(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。
     * <p>
     * 提示：
     * 1 <= n, size, mID <= 1000
     * 最多调用 allocate 和 free 方法 1000 次
     * @param: [int]
     * @return:
     * @Author: zhanglinxin
     * @date: 2025/2/25 07:54
     */
    Integer[] memory;

    public Solution202502(int n) {
        memory = new Integer[n];
    }

    public int allocate(int size, int mID) {
        if (size > memory.length) {
            return -1;
        }
        int count = 0;
        for (int i = 0; i < memory.length; i++) {
            if (memory[i] == null) {
                count++;
                if (count == size) {
                    for (int j = i - size + 1; j <= i; j++) {
                        memory[j] = mID;
                    }
                    return i - size + 1;
                }
            } else {
                count = 0;
            }
        }
        return -1;
    }

    public int freeMemory(int mID) {
        int count = 0;
        for (int i = 0; i < memory.length; i++) {
            if (memory[i] != null && memory[i] == mID) {
                memory[i] = null;
                count++;
            }
        }
        return count;
    }

    /**
     * @Description: 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
     * 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
     * 请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
     * <p>
     * 示例 1：
     * 输入：cost = [10, 15, 20]
     * 输出：15
     * 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
     * <p>
     * 示例 2：
     * 输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
     * 输出：6
     * 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
     * <p>
     * 提示：
     * 2 <= cost.length <= 1000
     * 0 <= cost[i] <= 999
     * @param: [int[]]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/25 08:10
     */
    public int minCostClimbingStairs2(int[] cost) {
        int pre1 = 0, pre2 = 0, cur = 0;
        for (int i = 2; i <= cost.length; i++) {
            // cur为爬到i阶楼梯的最小花费
            cur = Math.min(pre1 + cost[i - 1], pre2 + cost[i - 2]);
            pre2 = pre1;
            pre1 = cur;
        }
        return cur;
    }

    /**
     * @Description: 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     * <p>
     * 示例 1：
     * 输入：n = 3
     * 输出：["((()))","(()())","(())()","()(())","()()()"]
     * <p>
     * 示例 2：
     * 输入：n = 1
     * 输出：["()"]
     * @param: [int]
     * @return: java.util.List<java.lang.String>
     * @Author: zhanglinxin
     * @date: 2025/2/25 08:25
     */
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        dfs(list, "", n, n);
        return list;
    }

    public void dfs(List<String> list, String str, int left, int right) {
        if (left == 0 && right == 0) {
            list.add(str);
        }
        if (left > 0) {
            dfs(list, str + "(", left - 1, right);

        }
        if (right > left) {
            dfs(list, str + ")", left, right - 1);
        }

    }

    /**
     * @Description: 你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，
     * 也可以在浏览历史中后退 steps 步或前进 steps 步。
     * 请你实现 BrowserHistory 类：
     * BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
     * void visit(string url) 从当前页跳转访问 url 对应的页面  。执行此操作会把浏览历史前进的记录全部删除。
     * string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，
     * 那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
     * string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，
     * 那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。
     * <p>
     * 示例：
     * 输入：
     * ["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
     * [["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
     * 输出：
     * [null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]
     * <p>
     * 解释：
     * BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
     * browserHistory.visit("google.com");       // 你原本在浏览 "leetcode.com" 。访问 "google.com"
     * browserHistory.visit("facebook.com");     // 你原本在浏览 "google.com" 。访问 "facebook.com"
     * browserHistory.visit("youtube.com");      // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
     * browserHistory.back(1);                   // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
     * browserHistory.back(1);                   // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
     * browserHistory.forward(1);                // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
     * browserHistory.visit("linkedin.com");     // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
     * browserHistory.forward(2);                // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
     * browserHistory.back(2);                   // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
     * browserHistory.back(7);                   // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"
     * <p>
     * 提示：
     * 1 <= homepage.length <= 20
     * 1 <= url.length <= 20
     * 1 <= steps <= 100
     * homepage 和 url 都只包含 '.' 或者小写英文字母。
     * 最多调用 5000 次 visit， back 和 forward 函数。
     * @param: [java.lang.String]
     * @return:
     * @Author: zhanglinxin
     * @date: 2025/2/26 07:55
     */
    List<String> list;
    int visitNum = 0;

    public Solution202502(String homepage) {
        list = new ArrayList<>();
        list.add(homepage);
        visitNum = 0;
    }

    public void visit(String url) {
        while (list.size() > visitNum + 1) {
            list.removeLast();
        }
        list.add(url);
        visitNum++;
    }

    public String back(int steps) {
        visitNum = Math.max(visitNum - steps, 0);
        return list.get(visitNum);
    }

    public String forward(int steps) {
        visitNum = Math.min(visitNum + steps, list.size() - 1);
        return list.get(visitNum);
    }

    /**
     * @Description: 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 子数组 是数组中的一个连续部分。
     * <p>
     * 示例 1：
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     * <p>
     * 示例 2：
     * 输入：nums = [1]
     * 输出：1
     * <p>
     * 示例 3：
     * 输入：nums = [5,4,-1,7,8]
     * 输出：23
     * @param: [int[]]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/2/26 08:29
     */
    public int maxSubArray(int[] nums) {
        int sum = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum = Math.max(sum, 0);
            sum = sum + nums[i];
            max = Math.max(max, sum);
        }
        return max;
    }

    /**
     * @Description: 请你设计一个带光标的文本编辑器，它可以实现以下功能： 添加：在光标所在处添加文本。
     * 删除：在光标所在处删除文本（模拟键盘的删除键）。
     * 移动：将光标往左或者往右移动。
     * 当删除文本时，只有光标左边的字符会被删除。光标会留在文本内，也就是说任意时候 0 <= cursor.position <= currentText.length 都成立。
     * <p>
     * 请你实现 TextEditor 类：
     * TextEditor() 用空文本初始化对象。
     * void addText(string text) 将 text 添加到光标所在位置。添加完后光标在 text 的右边。
     * int deleteText(int k) 删除光标左边 k 个字符。返回实际删除的字符数目。
     * string cursorLeft(int k) 将光标向左移动 k 次。返回移动后光标左边 min(10, len) 个字符，其中 len 是光标左边的字符数目。
     * string cursorRight(int k) 将光标向右移动 k 次。返回移动后光标左边 min(10, len) 个字符，其中 len 是光标左边的字符数目。
     * <p>
     * 示例 1：
     * 输入：
     * ["TextEditor", "addText", "deleteText", "addText", "cursorRight", "cursorLeft", "deleteText", "cursorLeft", "cursorRight"]
     * [[], ["leetcode"], [4], ["practice"], [3], [8], [10], [2], [6]]
     * 输出：
     * [null, null, 4, null, "etpractice", "leet", 4, "", "practi"]
     * <p>
     * 解释：
     * TextEditor textEditor = new TextEditor(); // 当前 text 为 "|" 。（'|' 字符表示光标）
     * textEditor.addText("leetcode"); // 当前文本为 "leetcode|" 。
     * textEditor.deleteText(4); // 返回 4
     * // 当前文本为 "leet|" 。
     * // 删除了 4 个字符。
     * textEditor.addText("practice"); // 当前文本为 "leetpractice|" 。
     * textEditor.cursorRight(3); // 返回 "etpractice"
     * // 当前文本为 "leetpractice|".
     * // 光标无法移动到文本以外，所以无法移动。
     * // "etpractice" 是光标左边的 10 个字符。
     * textEditor.cursorLeft(8); // 返回 "leet"
     * // 当前文本为 "leet|practice" 。
     * // "leet" 是光标左边的 min(10, 4) = 4 个字符。
     * textEditor.deleteText(10); // 返回 4
     * // 当前文本为 "|practice" 。
     * // 只有 4 个字符被删除了。
     * textEditor.cursorLeft(2); // 返回 ""
     * // 当前文本为 "|practice" 。
     * // 光标无法移动到文本以外，所以无法移动。
     * // "" 是光标左边的 min(10, 0) = 0 个字符。
     * textEditor.cursorRight(6); // 返回 "practi"
     * // 当前文本为 "practi|ce" 。
     * // "practi" 是光标左边的 min(10, 6) = 6 个字符。
     * <p>
     * 提示：
     * 1 <= text.length, k <= 40
     * text 只含有小写英文字母。
     * 调用 addText ，deleteText ，cursorLeft 和 cursorRight 的 总 次数不超过 2 * 104 次。
     * <p>
     * 进阶：你能设计并实现一个每次调用时间复杂度为 O(k) 的解决方案吗？
     * @param: []
     * @return:
     * @Author: zhanglinxin
     * @date: 2025/2/27 07:44
     */
    class TextEditor {
        private StringBuilder text = new StringBuilder();
        private int textPoint = 0;

        public TextEditor() {
        }

        public void addText(String textToAdd) {
            text.insert(textPoint, textToAdd);
            textPoint += textToAdd.length();
        }

        public int deleteText(int k) {
            int delCount = Math.min(k, textPoint);
            text.delete(textPoint - delCount, textPoint);
            textPoint -= delCount;
            return delCount;
        }

        public String cursorLeft(int k) {
            textPoint = Math.max(textPoint - k, 0);
            int start = Math.max(textPoint - 10, 0);
            return text.substring(start, textPoint);
        }

        public String cursorRight(int k) {
            textPoint = Math.min(textPoint + k, text.length());
            int start = Math.max(textPoint - 10, 0);
            return text.substring(start, textPoint);
        }
    }

    class TextEditor2 {

        private final StringBuilder left = new StringBuilder();
        private final StringBuilder right = new StringBuilder();

        public TextEditor2() {

        }

        public void addText(String text) {
            left.append(text);
        }

        public int deleteText(int k) {
            k = Math.min(k, left.length());
            left.setLength(left.length() - k);
            return k;
        }

        public String cursorLeft(int k) {
            while (k > 0 && !left.isEmpty()) {
                right.append(left.charAt(left.length() - 1));
                left.setLength(left.length() - 1);
                k--;
            }

            return left.substring(Math.max(0, left.length() - 10), left.length());
        }

        public String cursorRight(int k) {
            while (k > 0 && !right.isEmpty()) {
                left.append(right.charAt(right.length() - 1));
                right.setLength(right.length() - 1);
                k--;
            }

            return left.substring(Math.max(0, left.length() - 10), left.length());
        }
    }

    /**
     * @Description: 设计一个支持下述操作的食物评分系统：
     * 修改 系统中列出的某种食物的评分。
     * 返回系统中某一类烹饪方式下评分最高的食物。
     * 实现 FoodRatings 类：
     * FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化系统。食物由 foods、cuisines 和 ratings 描述，长度均为 n 。
     * foods[i] 是第 i 种食物的名字。
     * cuisines[i] 是第 i 种食物的烹饪方式。
     * ratings[i] 是第 i 种食物的最初评分。
     * void changeRating(String food, int newRating) 修改名字为 food 的食物的评分。
     * String highestRated(String cuisine) 返回指定烹饪方式 cuisine 下评分最高的食物的名字。如果存在并列，返回 字典序较小 的名字。
     * 注意，字符串 x 的字典序比字符串 y 更小的前提是：x 在字典中出现的位置在 y 之前，也就是说，要么 x 是 y 的前缀，
     * 或者在满足 x[i] != y[i] 的第一个位置 i 处，x[i] 在字母表中出现的位置在 y[i] 之前。
     * <p>
     * 示例：
     * 输入
     * ["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
     * [[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
     * 输出
     * [null, "kimchi", "ramen", null, "sushi", null, "ramen"]
     * <p>
     * 解释
     * FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
     * foodRatings.highestRated("korean"); // 返回 "kimchi"
     * // "kimchi" 是分数最高的韩式料理，评分为 9 。
     * foodRatings.highestRated("japanese"); // 返回 "ramen"
     * // "ramen" 是分数最高的日式料理，评分为 14 。
     * foodRatings.changeRating("sushi", 16); // "sushi" 现在评分变更为 16 。
     * foodRatings.highestRated("japanese"); // 返回 "sushi"
     * // "sushi" 是分数最高的日式料理，评分为 16 。
     * foodRatings.changeRating("ramen", 16); // "ramen" 现在评分变更为 16 。
     * foodRatings.highestRated("japanese"); // 返回 "ramen"
     * // "sushi" 和 "ramen" 的评分都是 16 。
     * // 但是，"ramen" 的字典序比 "sushi" 更小。
     * <p>
     * 提示：
     * 1 <= n <= 2 * 104
     * n == foods.length == cuisines.length == ratings.length
     * 1 <= foods[i].length, cuisines[i].length <= 10
     * foods[i]、cuisines[i] 由小写英文字母组成
     * 1 <= ratings[i] <= 108
     * foods 中的所有字符串 互不相同
     * 在对 changeRating 的所有调用中，food 是系统中食物的名字。
     * 在对 highestRated 的所有调用中，cuisine 是系统中 至少一种 食物的烹饪方式。
     * 最多调用 changeRating 和 highestRated 总计 2 * 104 次
     * @Author: zhanglinxin
     * @date: 2025/2/28 07:47
     */
    class FoodRatings {
        // 食物-烹饪
        private Map<String, String> cuisineMap = new HashMap<>();
        // 食物-评分
        private Map<String, Integer> ratingMap = new HashMap<>();
        // 烹饪-食物
        private Map<String, TreeSet<String>> foodMap = new HashMap<>();

        public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
            for (int i = 0; i < foods.length; i++) {
                cuisineMap.put(foods[i], cuisines[i]);
                ratingMap.put(foods[i], ratings[i]);
            }
            for (int i = 0; i < foods.length; i++) {
                // getOrDefault,如果键存在，则返回与该键关联的值，否则返回指定的默认值
                // 根据食物评分排名，评分相同，按照字典顺序排名
                TreeSet<String> treeSet = foodMap.getOrDefault(cuisines[i], new TreeSet<>((o1, o2) -> {
                    if (ratingMap.get(o1).equals(ratingMap.get(o2))) {
                        return o1.compareTo(o2);
                    }
                    return ratingMap.get(o2) - ratingMap.get(o1);
                }
                ));
                treeSet.add(foods[i]);
                foodMap.put(cuisines[i], treeSet);
            }
        }

        // 修改食物的评分
        public void changeRating(String food, int newRating) {
            // 获取烹饪方式
            String cuisine = cuisineMap.get(food);
            // 获取食物评分排名列表
            TreeSet<String> treeSet = foodMap.get(cuisine);
            // 移除食物
            treeSet.remove(food);
            // 修改评分
            ratingMap.put(food, newRating);
            // 添加食物，更新评分排名
            treeSet.add(food);
        }

        public String highestRated(String cuisine) {
            return foodMap.get(cuisine).first();
        }
    }


    Solution202502() {
    }

    public static void main(String[] args) {
        Solution202502 solution202502 = new Solution202502();
    }
}
